

#ifndef LINKED_LIST_H
#define LINKED_LIST_H



class LinkedListException{
	public:
		LinkedListException(){}
};


template <typename T>
class LinkedListNode
{
public:
	LinkedListNode(const T& val){
		m_value = val;
		m_next = NULL;
	}
	T m_value;
	LinkedListNode *m_next;
};


template <typename T>
class LinkedList
{
public:
	LinkedList(){
		m_first = NULL;
		m_last = NULL;
		m_size = 0;
	}

	virtual ~LinkedList(){
		LinkedListNode<T> *node = m_first, *temp;
		while(node != NULL)
		{
			temp = node->m_next;
			delete(node);
			node = temp;
		}
	}


	int size(){
		return m_size;
	}

	// Purpose : Insert an element at the beginning of the linked list
	void insertFirst(T& value){
		LinkedListNode<T> *node = new LinkedListNode<T>(value);

		if(m_first == NULL){
			m_first = m_last = node;
		}
		else{
			node->m_next = m_first;
			m_first = node;
		}
		m_size++;
	}

	// Purpose : Inserts an element at the end of the linked list
	void insertLast(T& value){
		LinkedListNode<T> *node = new LinkedListNode<T>(value);

		if(m_first == NULL){
			m_first = m_last = node;
		}
		else{
			m_last->m_next = node;
			m_last = node;
		}
		m_size++;
	}

	// Purpose : removes the node at the pos position in the linked list
	void remove(int pos){
		LinkedListNode<T> *node = m_first, *temp;
		int i;
		if(pos >= m_size)
			throw LinkedListException();

		for(i=0; i<pos-1; i++, node=node->m_next);
		if(m_size == 1){
			temp = m_first;
			m_first = NULL;
			m_last = NULL;
			delete(temp);
		}
		else if(pos == 0){
			temp = m_first;
			m_first = m_first->m_next;
		}
		else if(pos == m_size-1){
			temp = m_last;
			m_last = node;
		}else{
			temp = node->m_next;
			node->m_next = node->m_next->m_next;
		}
		delete(temp);
		m_size--;
	}

	// Purpose : Gets the size of the linked list
	T& at(int pos) const{
		LinkedListNode<T> *node = m_first;
		int i;
		if(pos >= m_size)
			throw LinkedListException();
		for(i=0; i<pos; i++, node=node->m_next);
		return node->m_value;
	}

private:
	int m_size;
	LinkedListNode<T> *m_first;
	LinkedListNode<T> *m_last;
};

#endif


